package com.zyk.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * https://leetcode-cn.com/problems/validate-binary-tree-nodes/
 *
 * @author zhangsan
 * @date 2021/3/31 14:53
 */
public class C1361 {


    // N + N + N
    /** 先找根节点, 再来一次BFS */
    public static boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        HashSet<Integer> set = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        // 找到根节点, 即入度为0的节点
        int[] help = new int[n];
        for (int i = 0; i < n; i++) {
            if(leftChild[i] != -1) {
                help[leftChild[i]]++;
            }
            if(rightChild[i] != -1) {
                help[rightChild[i]]++;
            }
        }
        boolean oneRoot = true;
        int root = -1;
        // help 表存放的是 下标i的节点的入度, 入度超过2不是二叉树, 只有一个入度为0(根节点), 若有两个则不是二叉树
        for (int i = 0; i < help.length; i++) {
            if(help[i] > 1){
                // 入度超过2不是二叉树
                return false;
            }else if(help[i] == 0) {
                // root
                if(oneRoot) {
                    root = i;
                    oneRoot = false;
                }else {
                    // 走到这步说明有多个根节点, return false
                    return false;
                }
            }
        }
        if(root == -1) {
            return false;
        }
        set.add(root);
        queue.add(root);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if(leftChild[cur] != -1) {
                if(set.contains(leftChild[cur])) {
                    return false;
                }
                set.add(leftChild[cur]);
                queue.add(leftChild[cur]);
            }
            if(rightChild[cur] != -1) {
                if(set.contains(rightChild[cur])) {
                    return false;
                }
                set.add(rightChild[cur]);
                queue.add(rightChild[cur]);
            }
        }
        return set.size() == n;
    }

    public static boolean validateBinaryTreeNodes2(int n, int[] leftChild, int[] rightChild) {

        UnionFind unionFind = new UnionFind(n);
        boolean[] hasHead = new boolean[n];
        for (int i = 0; i < n; i++) {
            // 在这一路 i和它的左右孩子合并到并查集中, 如果他们之前就在一个集中, 那就不是一个有效二叉树
            if(leftChild[i] != -1) {
                if(unionFind.isSameSet(i, leftChild[i]) || hasHead[leftChild[i]] ) {
                    return false;
                }
                unionFind.union(i, leftChild[i]);
                hasHead[leftChild[i]] = true;
            }
            if(rightChild[i] != -1) {
                if(unionFind.isSameSet(i, rightChild[i]) || hasHead[rightChild[i]] ) {
                    return false;
                }
                unionFind.union(i, rightChild[i]);
                hasHead[rightChild[i]] = true;
            }
        }
        return unionFind.sets() == 1;
    }

    /** 查集小结构 */
    public static class UnionFind {
        int[] parents;
        // size数组决定把谁关联到谁上边减轻移动过程
        int[] size;
        // help数组是为了加速,找父过程
        int[] help;
        int sets;

        public UnionFind(int n) {
            parents = new int[n];
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }

            size = new int[n];
            Arrays.fill(size, 1);

            help = new int[n];
            sets = n;
        }

        /** 寻找他所在的集的头节点 */
        private int findHead(int i) {
            // 重头戏, 查找父的过程要快. 在查找的时候把他们都直接指向头节点. 这样后序查找就能很快地找到
            int helpIndex = 0;
            while ( parents[i] != i ) {
                help[helpIndex++] = i;  // 记录寻找一路过程中的元素
                i = parents[i];
            }
            // 最后i来到了头元素, 把这里一路的元素直接指向i
            while (helpIndex > 0) {
                parents[ help[--helpIndex] ] = i;
            }
            return i;       // 返回这个方法要找的东西
        }

        /** 是否同一组 */
        public boolean isSameSet(int a, int b) {
            return findHead(a) == findHead(b);
        }


        public void union(int i, int j) {
            // 找到他俩的头
            int iHead = findHead(i);
            int jHead = findHead(j);
            if(iHead != jHead) {
                // 不在一起开始合并, 看谁的元素少, 谁移动
                if(size[iHead] >= size[jHead]) {
                    // i的大, 移动j所在的并查集
                    parents[jHead] = iHead;
                    size[iHead] += size[jHead];
                    size[jHead] = 0;
                }else {
                    // j的大, 移动i所在的并查集
                    parents[iHead] = jHead;
                    size[jHead] += size[iHead];
                    size[iHead] = 0;
                }
                sets--; // 移动完了,别忘记把集的数量-1;
            }
        }

        /** 内部现在有多少个集 */
        public int sets() {
            return sets;
        }
    }

    // for test
    public static void main(String[] args) {

        // 3
        // [1,-1,-1]
        // [-1,-1,1]
//        int n = 3;
//        int[] leftChild = {1,-1,-1};
//        int[] rightChild = {-1,-1,1};
        int n = 4;
        int[] leftChild = {1,-1,3,-1};
        int[] rightChild = {2,-1,-1,-1};

        System.out.println(validateBinaryTreeNodes(n, leftChild, rightChild));
        System.out.println(validateBinaryTreeNodes2(n, leftChild, rightChild));
    }

}
